{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Лекция 5. Шаблоны"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Выдать домашнее задание по полиному"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Какая идея стоит за шаблонами"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ранее мы познакомились с возможностью перегрузки функций. Давайте вспомним её на примере swap:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// поменять местами два int\n",
    "void my_swap(int& a, int& b)\n",
    "{\n",
    "    int tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;    \n",
    "}\n",
    "\n",
    "// поменять местами два short\n",
    "void my_swap(short& a, short& b)\n",
    "{\n",
    "    short tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "// поменять местами два float\n",
    "void my_swap(float& a, float& b)\n",
    "{\n",
    "    float tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "...\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вечер начинает быть томным ..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Для решения проблем написания одинакового кода придуманы шаблоны:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// напишем шаблон - как должна выглядеть функция\n",
    "template<typename T>\n",
    "void my_swap(T& a, T& b)\n",
    "{\n",
    "    Type tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Применение шаблона:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int a = 3, b = 5;\n",
    "\n",
    "// вызов my_swap(int&, int&), тип T указывается программистом явно\n",
    "my_swap<int>(a, b);\n",
    "\n",
    "// вызов my_swap(int&, int&), тип T выводится компилятором автоматически\n",
    "my_swap(a, b); \n",
    "\n",
    "\n",
    "float x = 3.f, y = 5.f;\n",
    "my_swap(x, y);\n",
    "my_swap<float>(x, y);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Важное свойство шаблонов по сравнению с перегрузкой функций: шаблон компилируется только тогда, когда он вызывается. И компилируется только для тех типов, для которых он вызывается.\n",
    "\n",
    "_но в каждом cpp-файле шаблон компилируется снова и снова_\n",
    "\n",
    "Показать пример на godbolt.org, позакомментировать функции, продемонстрировать разницу в выхлопе компилятора."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__ ((noinline)) myswap(T& a, T& b)\n",
    "{\n",
    "    T tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    int i1 = 3, i2 = 5;\n",
    "    myswap(i1, i2);\n",
    "\n",
    "    float f1 = 3.f, f2 = 5.f;\n",
    "    myswap(f1, f2);\n",
    "\n",
    "    double d1 = 3., d2 = 5.;\n",
    "    myswap(d1, d2);\n",
    "\n",
    "    std::string s1 = \"abc\", s2 = \"def\";\n",
    "    myswap(s1, s2);\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Особенности шаблонов по сравнению с перегруженными функциями:\n",
    "* компилируется только то, что инстанциируется в коде\n",
    "* компилируется столько раз, в скольки единицах трансляции инстанциируется:\n",
    "    * можно в одном cpp-файле 10 раз позвать myswap(int&, int&) - эта функция скомпилируется единожды\n",
    "    * можно в 10 cpp-файлах один раз позвать myswap(int&, int&) - эта функция скомпилируется 10 раз\n",
    "* накладные расходы во время компиляции на кодогенерацию при истанциации\n",
    "* позволяет компилятору агрессивнее оптимизировать. Раскомментировать `__attribute__((noinline))` из примера и показать какой код сгенерирует компилятор. Объяснить, почему.\n",
    "* позволяет нарушать ODR"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Коротко:\n",
    "\n",
    "* (+) меньше кода\n",
    "* (+) быстрее\n",
    "* (-) дольше компилируется\n",
    "* (-) сложнее писать"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопросы__:\n",
    "* Где поместить шаблонную функцию, которую нужно использовать в разных cpp-файлах?\n",
    "* Где поместить её реализацию?\n",
    "* Может ли шаблонная функция содержать некомпилирующийся код?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Специализация"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Перегрузка функций позволяла сделать `myswap` у `std::string` более эффективно, без лишнего копирования памяти:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void myswap(int& a, int& b) { ... }\n",
    "void myswap(short& a, short& b) { ... }\n",
    "\n",
    "void myswap(std::string& a, std::string& b)\n",
    "{\n",
    "    a.swap(b);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Шаблоны тоже позволяют специализировать поведение функций, если наложить на шаблонный параметр ограничение, например:\n",
    "\n",
    "(закинуть этот код на godbolt, показать во что компилируется программа)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <string>\n",
    "\n",
    "template<typename T>\n",
    "void __attribute__ ((noinline)) myswap(T& a, T& b)\n",
    "{\n",
    "    T tmp = a;\n",
    "    a = b;\n",
    "    b = tmp;\n",
    "}\n",
    "\n",
    "template<>\n",
    "void __attribute__ ((noinline)) myswap<std::string>(std::string& a, std::string& b)\n",
    "{\n",
    "    a.swap(b);\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    int i1 = 3, i2 = 5;\n",
    "    myswap(i1, i2);\n",
    "\n",
    "    float f1 = 3.f, f2 = 5.f;\n",
    "    myswap(f1, f2);\n",
    "\n",
    "    double d1 = 3., d2 = 5.;\n",
    "    myswap(d1, d2);\n",
    "\n",
    "    std::string s1 = \"abc\", s2 = \"def\";\n",
    "    myswap(s1, s2);\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во-первых, шаблон может иметь несколько параметров, а во-вторых, параметры не обязаны быть типами. Они могут быть, например, целыми числами:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<int N, typename T>\n",
    "T add_value(T x)\n",
    "{\n",
    "    return x + N;\n",
    "}\n",
    "\n",
    "int a = add_value<5>(100);\n",
    "\n",
    "// 1. шаблон специфицирован программистом частично, тип Т компилятор определит сам\n",
    "// 2. параметром шаблона выступает целое число.\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: Какую информацию здесь компилятор использует, чтобы вывести тип `T`?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Шаблонные классы"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Аналогично функциям, классы тоже могут быть шаблонными:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример структуры:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// N-мерный вектор из курса линейной алгебры типа T\n",
    "template<typename T, int N>\n",
    "struct VectorN\n",
    "{\n",
    "    T data[N];\n",
    "};\n",
    "// TODO: обсудить / нарисовать как эта структура выглядит в памяти. Чему равен sizeof.\n",
    "\n",
    "// в качестве примера запишем операции сложения и умножения для таких векторов\n",
    "\n",
    "template<typename T, int N>\n",
    "VectorN<T, N> operator +(const VectorN<T, N>& l, const VectorN<T, N>& r)\n",
    "{\n",
    "    VectorN<T, N> rv;\n",
    "    for (int i = 0; i < N; ++i)\n",
    "        rv.data[i] = l.data[i] + r.data[i];\n",
    "    return rv;    \n",
    "}\n",
    "\n",
    "template<typename T, int N>\n",
    "T operator * (const VectorN<T, N>& l, const VectorN<T, N>& r)\n",
    "{\n",
    "    T rv = 0;\n",
    "    for (int i = 0; i < N; ++i)\n",
    "        rv += l.data[i] * r.data[i];\n",
    "    return rv;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример класса:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<typename T, int N>\n",
    "class RoundRobinQueue\n",
    "{\n",
    "private:\n",
    "    std::array<T, N> arr;\n",
    "    int begin_ix = 0;\n",
    "    int end_ix = 0;\n",
    "\n",
    "public:\n",
    "    static int next_ix(const int ix) noexcept\n",
    "    {\n",
    "        return (ix + 1) % N;\n",
    "    }\n",
    "    \n",
    "    void push(const T& item)\n",
    "    {\n",
    "        arr[end_ix] = item;\n",
    "        end_ix = next_ix(end_ix);\n",
    "    }\n",
    "    \n",
    "    T pop()\n",
    "    {\n",
    "        T item = arr[begin_ix];\n",
    "        begin_ix = next_ix(begin_ix);\n",
    "        return item;\n",
    "    }\n",
    "\n",
    "    bool empty() const noexcept\n",
    "    {\n",
    "        return begin_ix == end_ix;\n",
    "    }\n",
    "    \n",
    "    bool full() const noexcept\n",
    "    {\n",
    "        return next_ix(end_ix) == begin_ix;\n",
    "    }\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Его использование:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "RoundRobinQueue<int, 100> queue;\n",
    "queue.push(1);\n",
    "queue.push(2);\n",
    "queue.push(3);\n",
    "queue.pop();  // 1\n",
    "queue.pop();  // 2\n",
    "queue.pop();  // 3\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: Как обходить вопрос, что программист может позвать ещё один `queue.pop` ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А ещё класс может иметь шаблонный метод, почему бы и нет."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <array>\n",
    "#include <string>\n",
    "\n",
    "template<typename T, int N>\n",
    "class RoundRobinQueue\n",
    "{\n",
    "private:\n",
    "    std::array<T, N> arr;\n",
    "    int begin_ix = 0;\n",
    "    int end_ix = 0;\n",
    "\n",
    "public:\n",
    "    static int next_ix(const int ix) noexcept\n",
    "    {\n",
    "        return (ix + 1) % N;\n",
    "    }\n",
    "\n",
    "    template<typename U>\n",
    "    void push(const U& item)\n",
    "    {\n",
    "        arr[end_ix] = item;\n",
    "        end_ix = next_ix(end_ix);\n",
    "    }\n",
    "\n",
    "    T pop()\n",
    "    {\n",
    "        T item = arr[begin_ix];\n",
    "        begin_ix = next_ix(begin_ix);\n",
    "        return item;\n",
    "    }\n",
    "\n",
    "    bool empty() const noexcept\n",
    "    {\n",
    "        return begin_ix == end_ix;\n",
    "    }\n",
    "\n",
    "    bool full() const noexcept\n",
    "    {\n",
    "        return next_ix(end_ix) == begin_ix;\n",
    "    }\n",
    "};\n",
    "\n",
    "std::string f()\n",
    "{\n",
    "    RoundRobinQueue<std::string, 100> queue;\n",
    "    queue.push(std::string(\"run\"));\n",
    "    queue.push(\"Forest\");\n",
    "    queue.push(\"run\");\n",
    "    return queue.pop();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Закинуть пример на godbolt, показать, что генерируется 3 метода `push`, не забыть убрать оптимизации"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Шаблонный конструктор - пожалуйста! Это ведь тоже метод"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Шаблонный деструктор... пожалуй, нет, хватит."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопрос__: какой подвох есть у такого шаблона?\n",
    "\n",
    "```c++\n",
    "template<typename T, typename U>\n",
    "struct is_same\n",
    "{\n",
    "    static const bool value = false;\n",
    "};\n",
    "\n",
    "template<typename T>\n",
    "struct is_same<T, T>\n",
    "{\n",
    "    static const bool value = true;\n",
    "};\n",
    "\n",
    "is_same<int, int>\n",
    "is_same<int, float>\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Частичная специализация шаблонов (для классов)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Например, можно прописать alias:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<int N>\n",
    "using RoundRobinStringsQueue = RoundRobinQueue<std::string, N>;\n",
    "\n",
    "\n",
    "RoundRobinStringsQueue<100> queue;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А можно и изменить поведение класса"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<int N>\n",
    "class RoundRobinQueue<std::string, N>\n",
    "{\n",
    "private:\n",
    "    std::string arr[N];  // !!! here\n",
    "    int begin_ix = 0;\n",
    "    int end_ix = 0;\n",
    "\n",
    "public:\n",
    "    ...\n",
    "    \n",
    "    template<typename U>\n",
    "    void push(const U& item)\n",
    "    {\n",
    "        std::cout << \"push!\";  // !!! here\n",
    "        arr[end_ix] = item;\n",
    "        end_ix = next_ix(end_ix);\n",
    "    }\n",
    "    \n",
    "    ...\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Такие сложности могут пригодиться для compile-time полиморфизма. С его классическим применением - type traits-ами - познакомимся позже."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### just for fun: compile-time факториал"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Теперь мы разбираемся в шаблонах достаточно чтобы посчитать факториал во время компиляции на шаблонах (разобрать пример, показать результат в godbolt).\n",
    "\n",
    "Примечание: C++ значительно эволюционировал, и больше во время компиляции таким образом вычисления не проводят. Пример исключительно ученический. Compile-time вычисления будут, возможно, рассмотрены в курсе далее."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<unsigned N>\n",
    "struct Factorial\n",
    "{\n",
    "    static const int value = N * Factorial<N - 1>;\n",
    "};\n",
    "\n",
    "template<>\n",
    "struct Factorial<0>\n",
    "{\n",
    "    static const int value = 1;\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    return Factorial<10>::value;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопросы__:\n",
    "* Что делает следующий пример?\n",
    "\n",
    "```c++\n",
    "#include <cstdio>\n",
    "\n",
    "template<unsigned N>\n",
    "struct f\n",
    "{\n",
    "    static const int value = f<N-1>::value + f<N-2>::value;\n",
    "};\n",
    "\n",
    "template<>\n",
    "struct f<0>\n",
    "{\n",
    "    static const int value = 0;\n",
    "};\n",
    "\n",
    "template<>\n",
    "struct f<1>\n",
    "{\n",
    "    static const int value = 1;\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    printf(\"%i\\n\", f<45>::value);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Во второй части курса про шаблоны:\n",
    "* SFINAE\n",
    "* variadic templates\n",
    "* type traits\n",
    "* tag dispatching (возможно)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
